
//986.区间列表的交集
class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        //[a1,a2]和[b1,b2]a2<=b1||a1<=b2时有交集,找出交集,并将a2和b2中小的向前移
        //当b1>a2||a1>b2时没有交集
        //对于a1>b2,将b2增大来实现交集
        //对于b1>a2,将a2增大来找交集

        int i=0,j=0;
        int n=firstList.size(),m=secondList.size();
        vector<vector<int>> ret;
        while(i<n&&j<m)
        {
            if(firstList[i][0]>secondList[j][1]) j++;
            else if(firstList[i][1]<secondList[j][0]) i++;
            else 
            {
                int begin=max(firstList[i][0],secondList[j][0]);
                int end=min(firstList[i][1],secondList[j][1]);
                ret.push_back({begin,end});

                if(firstList[i][1]>secondList[j][1]) j++;
                else i++;
            }
        }
        return ret;
    }
};